BIT Algo/2. Zajęcia/Zadanie 6. (tablica zwierająca wiele powtórzeń - sortowanie w czasie O(n log(log(n)))).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Dana jest tablica z $n$ liczbami całkowitymi. Zawiera ona bardzo dużo powtórzeń - co więcej, zaledwie $O(log(n))$ liczb jest unikatowe (reszta to powtórzenia). Napisz algorytm, który w czasie $O(n \\cdot log(log(n)))$ posortuje taką tablicę."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# I Sposób"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Omówienie algorytmu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### 1. krok - odnalezienie unikatowych wartości"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Najpierw tworzymy pomocniczą tablicę, w której będziemy przechowywać $log(n)$ unikatowych wartości. Ponieważ całkowita złożoność obliczeniowa algorytmu ma wynieść $O(n \\cdot log(log(n)))$, czynnik $ og(log(n))$ sugeruje nam, że konieczne będzie użycie wyszukiwania binarnego na tablicy unikatowych wartości. Takie wyszukiwanie działa w czasie $O(log(k))$, gdzie $k$ - liczba elementów przeszukiwanej posortowanej tablicy, ale w naszym przypadku ta tablica ma rozmiar $k = log(n)$, więc otrzymujemy złożoność jednego binarnego przeszukania tablicy równą $O(log(log(n)))$. Ponieważ początkowo nie mamy utworzonej tej tablicy, idąc po kolejnych wartościach źródłowej n-elementowej tablicy, musimy sprawdzać, czy bieżąca wartość znajduje się już w tablicy unikatów. Jeżeli nie, konieczne jest jej umieszczenie w tablicy, a następnie przywrócenie niemalejącego porządku wartości w tej tablicy. Najłatwiej jest to uczynić, korzystając ze zmodyfikowanego Insertion Sorta, którego wywołamy tylko dla ostatniej (nowo dodanej) wartości do tablicy. Wynikiem takiej operacji będzie przesunięcie wartości w lewo na odpowiednią pozycję w tablicy, przy czym wszystkie wartości większe od nowo dodanej zostaną przesunięte w prawą stronę. Taka operacja może się wydawać mało efektywna, ale tablica ma maksymalnie wielkość $log(n)$ elementów, więc wstawianie do tablicy będziemy przeprowadzać jedynie $log(n)$ razy, więc w najgorszym przypadku (gdy konieczne będzie przesunięcie każdej z dodanych wartości na początek tablicy unikatów) złożoność obliczeniowa wymagana do utworzenia tej tablicy będzie równa $O(log^2(n))$. Warto jeszcze zauważyć, że wstawianie do tablicy zostanie wykonane jedynie, jeżeli obecnie sprawdzana wartość nie występuje w tablicy unikatów, więc finalna złożoność obliczeniowa 1. kroku wyniesie: $O(n \\cdot log(log(n)) + log^2(n)) = O(n \\cdot log(log(n)))$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### 2. krok - zliczenie wystąpień każdej z wartości"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tu na myśl przychodzi od razu algorytm sortowania Counting Sort. Zauważmy jednak, że nie wiemy nic o zakresie liczb, więc w szczególności mogą to być liczby ujemne rzędu $-10^9$ lub jeszcze mniejsze i podobnie liczby dodatnie rzędu $10^9$ lub większe. Counting Sort (który nie wykorzystuje Hash Map do przechowywania zliczonych wartości, a na razie nie możemy ich wykorzystywać) wymaga zaalokowania ciągłego obszaru pamięci od wartości najmniejszej do największej włącznie. Może to spowodować zużycie ogromnej ilości pamięci operacyjnej lub jej przepełnienie, dlatego, pamiętając o wymaganej złożoności obliczeniowej, wykorzystamy nieco wolniejsze, ale wciąż wystarczająco szybkie rozwiązanie. Mianowicie, stworzymy nową tablicę o rozmiarze identycznym do wcześniej utworzonej tablicy unikatowych wartości, w której będziemy przechowywać liczby wystąpień kolejnych wartości od najmniejszej do największej. Potrzebna nam jest funkcja, która będzie dla danej wartości zwracała indeks odpowiedniej komórki tablicy, pod którym należy zwiększyć licznik. Możemy zauważyć, że da się wykorzystać do tego celu poprzednio utworzoną tablicę posortowanych unikatów (długości $log(n)$). Sama funkcja będzie pobierała bieżącą wartość z tablicy wyjściowej (tej, jaką otrzymaliśmy na wejściu do posortowania) i z pomocą wyszukiwania binarnego, przeszukiwała posortowaną tablicę unikatów (w czasie $O(log(log(n))$), zwracając na koniec indeks danej wartości w tej tablicy unikatów. Następnie pod tym samym indeksem, pod którym znajduje się dana unikatowa wartość, będziemy zwiększać licznik w tablicy $counts$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### 3. krok - przepisanie wartości do tablicy wyjściowej"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Teraz pozostała najłatwiejsza część algorytmu, czyli przepisanie wartości w odpowiedniej kolejności. Jest to o tyle łatwe, że mamy tablicę posortowanych wartości i tablicę liczby ich wystąpień, dlatego możemy po prostu liniowo (w czasie $O(log(n))$, bo rozmiar tablicy unikatów wynosi $log(n)$) przeglądać kolejne wartości z tablicy unikatów i umieszczać ich tyle w wejściowej tablicy, ile wynosi licznik odpowiadający danej wartości (ten sam indeks w tablicy liczników, co w tablicy unikatów). Łącznie ta operacja przepisywania wszystkich wartości zajmie czas $O(n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def crazy_sort(arr):\n",
    "    unique = []\n",
    "    # Look for unique numbers and store them in a unique array\n",
    "    for val in arr:\n",
    "        idx = binary_search(unique, val)\n",
    "        # If a value is not stored in an unique array, insert this value\n",
    "        if idx < 0:\n",
    "            insert_element(unique, val)\n",
    "    \n",
    "    counts = [0] * len(unique)\n",
    "    # Count repetitions of each unique value\n",
    "    for val in arr:\n",
    "        idx = binary_search(unique, val)\n",
    "        counts[idx] += 1\n",
    "        \n",
    "#     print(counts, sum(counts), len(arr))\n",
    "    \n",
    "    arr_idx = 0\n",
    "    # Rewrite all values to the inintal array\n",
    "    for i in range(len(unique)):\n",
    "        for _ in range(counts[i]):\n",
    "            arr[arr_idx] = unique[i]\n",
    "            arr_idx += 1\n",
    "        \n",
    "    \n",
    "def insert_element(arr, val: 'inserted value'):\n",
    "    arr.append(val)\n",
    "    # Move all elements that are greater than a value inserted to the right\n",
    "    idx = len(arr) - 1\n",
    "    while idx > 0 and arr[idx - 1] > val:\n",
    "        arr[idx] = arr[idx - 1]\n",
    "        idx -= 1\n",
    "    # Place our value on the final position\n",
    "    arr[idx] = val\n",
    "        \n",
    "\n",
    "def binary_search(arr: 'sorted sequence', val: 'searched value') -> int:\n",
    "    left_idx = 0\n",
    "    right_idx = len(arr)-1\n",
    "    \n",
    "    while left_idx <= right_idx:\n",
    "        mid_idx = (left_idx + right_idx) // 2\n",
    "        if val > arr[mid_idx]:\n",
    "            left_idx = mid_idx + 1\n",
    "        else:\n",
    "            right_idx = mid_idx - 1\n",
    "            \n",
    "    return left_idx if left_idx < len(arr) and arr[left_idx] == val else -1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Funkcja testująca poprawność algorytmu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def test_sort(sorting_fn, *, \n",
    "              samples=20,         # A number of tests that will be performed\n",
    "              val_counts=(0, 50), # A minimum and maximum number of values to sort that will be generated\n",
    "              range_=(-100, 100), # A range which will be used to create a random list of values from this range\n",
    "              modifies_arr=True,  # Information whether an algorithm modifies the initial array or returns a sorted array\n",
    "              failed_only=False,  # Show only failed tests. Works only if no_results is set to False\n",
    "              print_out_fn=None,  # An user-defined function to print additional information. Works only if no_results is set to False\n",
    "              no_results=False    # When set to True, no results will be printed (useful only for benchmark)\n",
    "             ): \n",
    "    passed = 0                   \n",
    "    for i in range(samples):\n",
    "        random_lst = [random.randint(*range_) for _ in range(random.randint(*val_counts))]\n",
    "        random_lst_before = random_lst[:]\n",
    "        expected = sorted(random_lst)\n",
    "        output = sorting_fn(random_lst)\n",
    "        if not modifies_arr:\n",
    "            random_lst = output\n",
    "        is_correct = random_lst == expected\n",
    "        passed += is_correct\n",
    "        \n",
    "        if not no_results:\n",
    "            if not failed_only or (failed_only and not is_correct):\n",
    "                print(f'TEST #{i+1}:')\n",
    "                print(f'Before sorting: {random_lst_before}')\n",
    "                print(f'After sorting: {random_lst}')\n",
    "                print(f'Expected result: {expected}')\n",
    "                print(f'Test {\"PASSED\" if is_correct else \"FAILED\"}')\n",
    "                print(f'Current passed-to-tested ratio: {passed}/{i+1}')\n",
    "                if print_out_fn:\n",
    "                    print(f'========== Additional results after sorting  ==========')\n",
    "                    print_out_fn(random_lst)\n",
    "                print()\n",
    "                \n",
    "    if not no_results:\n",
    "        print(f'Sorting algorithms is {\"correct\" if passed == samples else \"wrong\"}')\n",
    "        print(f'Passed tests in total: {passed}/{samples}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "W poniższych testach nie mamy dokładnie $log(n)$ różnych wartości (lecz w przybliżeniu starałem się dobrać odpowiedni zakres), ale w przybliżeniu można ten algorytm przetestować, czy działa, a powinien działać dla każdego wejścia."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_sort(crazy_sort, range_=(-15, 15), val_counts=(0, 10_000), samples=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# II Sposób"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Omówienie algorytmu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Do posortowania tablicy wykorzystamy algorytm Quicker Sort. Ponieważ wiemy, że jest $log(n)$ różnych wartości, za każdym razem możemy się spodziewać, że wybrany przez nas pivot będzie się powtarzał w tablicy około $\\frac{n}{log(n)}$ razy. Jeżeli w funkcji partition będziemy dzielić tablicę na 3 części, z których pierwsza zawiera elementy mniejsze od pivota, druga mu równe, a trzecia większe od niego, w każdym wywołaniu rekurencyjnym funkcji sortującej będziemy odrzucać $\\frac{n}{log(n)}$ wartości równych pivotowi, które już napewno znajdują się na dobrej pozycji. Wynika stąd, że w najgorszym przypadku będziemy mieli $log(n)$ zejść rekurencyjnych, ponieważ $log(n) \\cdot \\frac{n}{log(n)} = n$ - będzie tak, gdy za każdym razem funkcja partition podzieli tablicę na elementy równe pivotowi, a elemtów większych od pivota (lub mniejszych) nie będzie wcale. Zatem całkowita złożoność wyniesie $n \\cdot log(log(n))$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def quicker_sort(arr):\n",
    "    _quicker_sort(arr, 0, len(arr) - 1)\n",
    "    \n",
    "\n",
    "def _quicker_sort(arr, left_idx, right_idx):\n",
    "    while left_idx < right_idx:\n",
    "        lt_pivot_last, gt_pivot_first = _partition(arr, left_idx, right_idx)\n",
    "        \n",
    "        # If a number of elements lower tha a pivot is greater than a number\n",
    "        # of elements greater than a pivot, sort recursively the shorter part\n",
    "        # of elements which are greater than a pivot\n",
    "        if lt_pivot_last - left_idx > right_idx - gt_pivot_first:\n",
    "            _quicker_sort(arr, gt_pivot_first, right_idx)\n",
    "            right_idx = lt_pivot_last  # I removed a tailing recursion\n",
    "        # Otherwise, sort a subarray of elementslower than a pivot first\n",
    "        # as it is shorter than a subarray of elements greater than a pivot\n",
    "        else:\n",
    "            _quicker_sort(arr, left_idx, lt_pivot_last)\n",
    "            left_idx = gt_pivot_first  # I removed a tailing recursion\n",
    "\n",
    "        \n",
    "def _partition(arr, left_idx, right_idx):\n",
    "    pivot = arr[left_idx]\n",
    "    \n",
    "    # Partition an array into 3 subarrays (lower than, equal to and\n",
    "    # greater than a pivot value)\n",
    "    i = left_idx     # A pointer of the first pivot\n",
    "    j = left_idx + 1 # A pointer of the element after the last pivot\n",
    "    k = j            # A pointer of the currently checked element \n",
    "    while k <= right_idx:\n",
    "        if arr[k] < pivot:\n",
    "            _two_swaps(arr, i, j, k)\n",
    "            i += 1\n",
    "            j += 1\n",
    "        elif arr[k] == pivot:\n",
    "            _one_swap(arr, j, k)\n",
    "            j += 1\n",
    "        k += 1\n",
    "        \n",
    "    # Return the last index of the subarray of elements lower than a pivot\n",
    "    # and the first index of the subarray of elements greater than a pivot\n",
    "    return i - 1, j\n",
    "\n",
    "    \n",
    "def _one_swap(arr, i, j):\n",
    "    # Swap two elements in an array\n",
    "    arr[i], arr[j] = arr[j], arr[i]\n",
    "    \n",
    "\n",
    "def _two_swaps(arr, i, j, k):\n",
    "    # Rotate right the elements of the indices specified\n",
    "    arr[k], arr[j], arr[i] = arr[j], arr[i], arr[k]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# test_sort(quicker_sort, range_=(-15, 15), val_counts=(0, 10_000), samples=1000, failed_only=True)\n",
    "test_sort(quicker_sort, range_=(-15, 15), val_counts=(0, 10_000), samples=1)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}